package tree;

/**
 * @Author leecho
 * @Date: 2021/10/28 18:05
 * @Version 1.0
 */

public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {4,3,6,5,7,8};
        AVLTree avlTree = new AVLTree();


        for (int i : arr) {
            avlTree.addNodeToTree(new AVLTreeNode(i));
        }

        avlTree.infixListTree();
        System.out.println();

        avlTree.avlTree();

        avlTree.infixListTree();
    }
}

class AVLTree{
    AVLTreeNode root;

    public void addNodeToTree(AVLTreeNode node){
        if (root == null)
            root = node;
        else {
            root.addNode(node);
        }
    }

    public void infixListTree(){
        if (root == null)
            System.out.println("空树，无法遍历");
        else
            root.infixList();
    }

    public void avlTree(){
        if (root == null)
            System.out.println("该树为空，无法平衡");
        else {
            root.avlTree();
        }
    }


}

/*
* 思路
* - 采用递归的方法添加结点
* - 平衡树，本身是有有序
* - 不允许有高度差如果有高度差则会进行旋转
*   - 右旋转和左旋转
*   - 如果左右两棵树高度差过大则会进行双旋转
* */
class AVLTreeNode{
    int no;
    AVLTreeNode left;
    AVLTreeNode right;

    public AVLTreeNode(int no) {
        this.no = no;
    }

    public int leftHigh(){
        if (this.left == null){
            return  0;
        } else {
            return this.left.high();
        }
    }

    public int rightHigh(){
        if (this.right == null){
            return  0;
        } else {
            return this.right.high();
        }
    }

    public int high(){
        return Math.max(this.left == null?  0 : this.left.high(),this.right == null? 0 : this.right.high()) + 1;
    }

    public void addNode(AVLTreeNode node){
        if (this.no > node.no){
            if (this.left == null){
                this.left = node;
            } else {
                this.left.addNode(node);
            }
        } else {
            if (this.right == null){
                this.right = node;
            } else {
                this.right.addNode(node);
            }
        }
    }

    public void infixList(){
        System.out.printf("%4d",this.no);
        if (this.left != null)
            this.left.infixList();
        if (this.right != null)
            this.right.infixList();
    }

    // 右旋转
    public void avlTree(){
        if ((this.rightHigh() - this.leftHigh() ) > 1){
            AVLTreeNode temp = new AVLTreeNode(this.no);
            temp.left = this.left;
            temp.right = this.right.left;
            this.no = this.right.no;
            this.right = this.right.right;
            this.left = temp;
        }
    }

    @Override
    public String toString() {
        return "AVLTreeNode{" +
                "no=" + no +
                '}';
    }
}
